package leetcode_day._2021._202109._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/19 22:13
 * 只有两个键的键盘
 * 算法：找规律  动态规划
 * 当 n 为质数的时候，最小操作次数是它本身
 * n 为合数的时候，最小操作次数是它的两个合数相加
 */
public class _19_650 {
    static int[] ans;
    static {
        ans = new int[101];
        int judge;
        for (int i = 2; i <= 100; i++) {
            judge = judge(i);
            if (judge == 1) ans[i] = i;
            else ans[i] = ans[judge] + ans[i / judge];
        }
    }

    public int minSteps(int n) {
        return ans[n];
    }
    static int judge(int n) {
        for (int i = 2; i < n / 2; i++) {
            if (n % i == 0) return i;
        }
        return 1;
    }

}
